/* 
 * This code is part of the smartlink project, see
 * 
 * 		http://code.google.com/p/smartlink/.
 * 
 * Copyright (C) 2008 Oliver Noelle
 * 
 * SmartLink is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * SmartLink is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with SmartLink.  If not, see <http://www.gnu.org/licenses/>.
 **/
package org.smartlink.search;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * originally based on the ideas presented in
 * http://www.heise.de/ct/english/97/04/386/
 * 
 * originally implemented and adapted in C++ and successfully used in yammi for
 * searching mp3s, see yammi.sourceforge.net
 * 
 * main class for performing a fuzzy search normal use in 4 steps:
 * <ol>
 * <li> step 1: create class + initialize with searchstring and params</li>
 * <li>step 2: checkNext(...) for all entries in database</li>
 * <li>step 3: (optional) newOrder(): reorder according to frequencies</li>
 * <li>step 4: getBestMatchesList() and do sth. with the result</li>
 * </ol>
 * 
 * class is robust against:
 * <ul>
 * <li>no matches at all (first found entries with sim=0 are returned) </li>
 * <li>searchstrings longer than MaximumEntryLength (=> cut off)</li>
 * <li>entries longer than MaximumEntryLength (=> cut off)</li>
 * <li> searchstrings with length 0 (no meaningful result, but no crash)</li>
 * <li>entries with length 0 (probably won't appear in result, which should be
 * okay)</li>
 * </ul>
 * beware of null-pointers in step 4 if best matches list is not completely
 * filled (not enough objects checked to fill list)
 */
public class FuzzySearch {

	/**
	 * maximum length of one searchable entry
	 */
	public static final int MAXIMUM_ENTRY_LENGTH = 200;

	/**
	 * how many hits to keep in best matches list
	 */
	private static final int NO_BEST_MATCHES = 200;

	/**
	 * maximum length ofused ngrams (more than 5 doesn't help a lot...)
	 */

	public static final int MAXIMUM_NGRAM_LENGTH = 5;

	protected int minSim;
	protected int noObjects = -1;

	// protected BestMatchEntry[] bmeList = new BestMatchEntry[NO_BEST_MATCHES];
	protected LinkedList<BestMatchEntry> bmeList = new LinkedList<BestMatchEntry>();

	private String preparedSearchString;
	/** ngram representation of the search string */
	NgramRep ngr;

	private int minNgramLen;

	private int maxNgramLen;

	// // compares two best match entries, considering their similarity value
	// static int bmeCompare(const void *elem1, const void *elem2)
	// {
	// int sim1=(*(BestMatchEntry**)elem1)->sim;
	// int sim2=(*(BestMatchEntry**)elem2)->sim;
	// return sim2-sim1;
	// }

	// creates and initializes class
	public FuzzySearch(int minNgramLen, int maxNgramLen) {
		if (noObjects != -1) { // object was already
			// initialized => we have to
			// clean up first
			// this is exactly the same as what the destructor does (but we
			// can't call it, can we?)
			// clean up bme-list
			// for(int i=0; i<NoBestMatches; i++) {
			// if (bme[i]!=0)
			// delete(bme[i]);
			// }
			// delete ngr;
		}

		// initialize list of best matches
		// for (int i = 0; i < NO_BEST_MATCHES; i++) {
		// bmeList[i] = null;
		// }
		noObjects = 0;
		minSim = -1;
		this.minNgramLen = minNgramLen;
		this.maxNgramLen = maxNgramLen;
	}

	public void prepareSearch(String searchStr) {
		preparedSearchString = prepareString(searchStr);
		ngr = new NgramRep(preparedSearchString, minNgramLen, maxNgramLen);
		bmeList.clear();
	}

	/**
	 * prepare a string:
	 * <ul>
	 * <li>enclose with spaces (better matches with matching word boundaries)</li>
	 * <li>to lowercase</li>
	 * <li>replace special characters like '-', '.', ... with space</li>
	 * <li>phonetic similarities => � -> ss, � -> oe, ...</li>
	 * <li>
	 * </ul>
	 * 
	 * @return the prepared string
	 */
	protected String prepareString(String originStr) {
		String src = originStr.toLowerCase();
		int srcLength = src.length();
		StringBuffer target = new StringBuffer(srcLength + 1);
		target.append(' '); // leading space
		for (int pos = 0; pos < srcLength; pos++) {
			switch (src.charAt(pos)) {
			// TODO: might get scrambled when read with wrong encoding
			case 'ä':
				target.append('a');
				target.append('e');
				break;
			case 'ü':
				target.append('u');
				target.append('e');
				break;
			case 'ö':
				target.append('o');
				target.append('e');
				break;
			// any separator chars => space
			case ',':
			case '-':
			case '.':
			case '(':
			case ')':
			case '*':
			case '/':
			case '@':
			case '\n':
				target.append(' ');
				break;
			case 'ß': // => ss
				target.append('s');
				target.append('s');
				break;
			default:
				target.append(src.charAt(pos));
			}
		}
		target.append(' '); // trailing space
		return target.toString();
	}

	/**
	 * perform searchstep
	 * 
	 * @return similarity coefficient between 0 and 1, -1 if invalid input
	 */
	public int checkNext(String nextEntry, Object objPtr) {
		int accuracy = 0;
		if (nextEntry == null || nextEntry.length() == 0) {
			return -1;
		}

		noObjects++;
		// prepare the string (leading space, lowercase, ...)
		String preparedNextEntry = prepareString(nextEntry);

		// for each ngram check match
		for (int i = 1; i <= ngr.noNgrams; i++) {
			NgramEntry ngram = ngr.ngrams[i];
			ngram.found = false;
			if (ngram.pre1 == null || (ngram.pre1.found == true && ngram.pre2.found == true)) {
				if (preparedNextEntry.contains(ngram.ngram)) {
					accuracy += ngram.entropy;
					ngram.frequency++;
					ngram.found = true;
				}
			}
		}
		accuracy = (accuracy * 1000) / ngr.maxScore;
		// Wenn Guete >= minimaler Wert in best matches liste: insert into list
		if (accuracy > minSim) {
			minSim = insertIntoOrderedList(accuracy, nextEntry, preparedNextEntry, objPtr);
		}
		return accuracy;
	}

	/**
	 * insert into best matches list (ordered by similarity)
	 * 
	 * @return the current threshold needed to get into the bme list (-1 if
	 *         there are still open slots)
	 */
	// private int xinsertIntoOrderedList(int similarity, String insertObject,
	// String preparedObject, Object objPtr) {
	// int i, j;
	// for (i = 0; i < NO_BEST_MATCHES; i++) {
	// if (bmeList[i] == null) {
	// bmeList[i] = new BestMatchEntry(similarity, insertObject,
	// preparedObject, objPtr);
	// break;
	// } else if (bmeList[i].sim < similarity) {
	// // delete last entry coz it will be dropped
	// if (bmeList[NO_BEST_MATCHES - 1] != null) {
	// // delete(bme[NoBestMatches-1]);
	// }
	// for (j = NO_BEST_MATCHES - 1; j > i; j--) {
	// bmeList[j] = bmeList[j - 1];
	// }
	// bmeList[i] = new BestMatchEntry(similarity, insertObject,
	// preparedObject, objPtr);
	// break;
	// }
	// }
	// if (bmeList[NO_BEST_MATCHES - 1] != null) {
	// return bmeList[NO_BEST_MATCHES - 1].sim;
	// } else {
	// return -1;
	// }
	// }
	/**
	 * insert into best matches list (ordered by similarity)
	 * 
	 * @return the current threshold needed to get into the bme list (-1 if
	 *         there are still open slots)
	 */
	private int insertIntoOrderedList(int similarity, String insertObject, String preparedObject, Object objPtr) {
		int index = 0;
		for (Iterator<BestMatchEntry> iterator = bmeList.iterator(); iterator.hasNext();) {
			BestMatchEntry entry = iterator.next();
			if (entry.sim < similarity) {
				break;
			}
			index++;
		}
		if (index < NO_BEST_MATCHES) {
			bmeList.add(index, new BestMatchEntry(similarity, insertObject, preparedObject, objPtr));
			if (bmeList.size() > NO_BEST_MATCHES) {
				bmeList.removeLast();
			}
		}
		return (bmeList.size() < NO_BEST_MATCHES) ? -1 : bmeList.getLast().sim;
	}

	// re-evaluate similarities (now with frequency) and re-order list of best
	// matches
	// void FuzzySearch::newOrder() {
	// if (noObjects==-1) return;
	// NgramEntry** ngs;
	// ngs=ngr->ngs;
	// int i,j;
	//
	// // step 0: calculate new entropy for all ngrams (depending on frequency)
	// ngr->maxScore=0;
	// for(i = 1; i <= ngr->noNgrams; i++) {
	// double prob=(double)ngs[i]->frequency/(double)noObjects; // probability
	// of appearance
	// double loggi=log(prob*100+1)/log(2.0); // clevere Formel...
	// int entro = 20+(ngs[i]->length)*10;
	// entro=(int) (entro*(1.0-loggi/10.0));
	// if (entro<1) entro=1;
	//
	// ngr->maxScore+=entro;
	// ngs[i]->entropy=entro;
	// }
	//
	// // step 1: calculate new similarity value for all best matches
	// for(j=0; j<NoBestMatches && bme[j]; j++) {
	// int accuracy=0;
	// for(i=1; i<=ngr->noNgrams; i++) {
	// ngs[i]->found=false;
	// if(ngs[ngs[i]->precondition[0]]->found==true &&
	// ngs[ngs[i]->precondition[1]]->found==true) {
	// if(strstr(bme[j]->preparedName, ngs[i]->str)) {
	// accuracy += (ngs[i]->entropy);
	// ngs[i]->found=true;
	// }
	// }
	// }
	// accuracy=accuracy*1000/ngr->maxScore;
	// bme[j]->sim=accuracy;
	// }
	//
	// // step 2: re-order list
	// qsort((void*)bme, j, sizeof(bme[0]), bmeCompare );
	// return;
	// }
	//

	// getters/setters
	// --------------------------------------

	public String getPreparedSearchString() {
		return preparedSearchString;
	}

	/**
	 * @return a sorted array of the best matches returns 0 if class was not
	 *         initialized
	 */
	public LinkedList<BestMatchEntry> getBestMatchesList() {
		return bmeList;
	}

}
